﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace Jenvin.Library.DataStruct
{
    public class CuckooDictionary<TKey, TValue> : IDictionary<TKey, TValue>
    {
        /// <summary>
        /// 默认初始大小
        /// </summary>
        static readonly int DEFAULT_INITIAL_CAPACITY = 16;
        /// <summary>
        /// 
        /// </summary>
        static readonly int MAXIMUM_CAPACITY = 1 << 30;
        /// <summary>
        /// 装填因子 
        /// </summary>
        static readonly float DEFAULT_LOAD_FACTOR = 0.75f;
        /// <summary>
        /// 最大的循环次数
        /// </summary>
        static readonly int LOOP_COUNT = 12;
        /// <summary>
        /// 循环次数超过 LOOP_COUNT 还没找到合理的位置.被认为是冲突的。放在conflictDic中
        /// </summary>
        private System.Collections.Generic.Dictionary<TKey, TValue> conflictDic = null;

        private IEqualityComparer<TKey> comparer;

        private Func<TKey,int> hash1 = null;

        private Func<TKey,int> hash2 = null;

        private Entry[] entries;
        private float loadFactor = 0;
        private int threshold = 0;
        private int size = 0;
        private class Entry
        {
            public TKey key;           // Key of entry
            public TValue value;         // Value of entry 
        }

        public CuckooDictionary()
            : this(DEFAULT_INITIAL_CAPACITY, null, DEFAULT_LOAD_FACTOR, null,
               (x) => HashAlgorithms.APHash(x.ToString()))
        {

        }

        public CuckooDictionary(int capacity, IEqualityComparer<TKey> comparer, float loadFactor,
            Func<TKey,int> h1, Func<TKey,int> h2)
        {
            //check args
            if (capacity < 0) throw new ArgumentException("capacity");
            if (loadFactor < 0) throw new ArgumentException("loadFactor");
            if (loadFactor > 1) throw new ArgumentException("loadFactor");
            if (h1 == null)
                h1 = (x) => comparer.GetHashCode(x);
            if (comparer == null) comparer = EqualityComparer<TKey>.Default;
            if (h2 == null) throw new ArgumentException("h2");


            this.loadFactor = loadFactor;
            threshold = capacity;
            //实际容量
            int actual = (int)Math.Ceiling(capacity / loadFactor);
            entries = new Entry[actual];
            hash1 = h1;
            hash2 = h2;
            this.comparer = comparer;
            conflictDic = new System.Collections.Generic.Dictionary<TKey, TValue>();
        }

        private int Hash(Func<TKey,int> hash, TKey key)
        {
            return (hash(key)&0x7fffffff )% entries.Length;
        }

        private void VerifyKey(object key)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key 不能为空");
            }

            if (!(key is TKey))
            {
                throw new ArgumentException("key类型不正确");
            }
        }

        private static void VerifyValueType(object value)
        {
            if ((value is TValue) || (value == null && !typeof(TValue).IsValueType))
            {
                return;
            }
            throw new ArgumentException("valu 类型不正确");
        }

        #region IDictionary<TKey,TValue> 成员

        public void Add(TKey key, TValue value)
        {
            Insert(key, value, false);
            if (size > threshold)//大于临界直。进行一次扩容
                Resize(2 * entries.Length);
        }

        private void Insert(TKey key, TValue value, bool isResize)
        {
            //如果存在。直接返回
            if (this.ContainsKey(key))
                return;

            if (!PutEntry(new CuckooDictionary<TKey, TValue>.Entry() { key = key, value = value }))
            {
                conflictDic.Add(key, value);//未插入成功。加入conflictDic
            }
            if (!isResize)
                size++;
        }

        private void Resize(int capacity)
        {
            Entry[] oldEntries = entries;
            System.Collections.Generic.Dictionary<TKey, TValue> oldConflictDic = this.conflictDic;

            int oldCapacity = oldEntries.Length;
            if (oldCapacity >= MAXIMUM_CAPACITY)
            {
                threshold = Int32.MaxValue;
                return;
            }

            entries = new Entry[capacity];
            this.conflictDic = new System.Collections.Generic.Dictionary<TKey, TValue>();
            foreach (Entry e in oldEntries)
            {
                if (e != null)
                    Insert(e.key, e.value, true);
            }
            foreach (KeyValuePair<TKey, TValue> kvp in oldConflictDic)
            {
                Insert(kvp.Key, kvp.Value, true);
            }

            this.threshold = (int)Math.Ceiling(capacity * this.loadFactor);
        }
        private bool PutEntry(Entry entry)
        {
            int loop = 0;
            Entry current = entry;

            int pos = Hash(hash1, current.key);

            while (current != entry || loop < LOOP_COUNT)
            //增加 LOOP_COUNT 限制 和conflictDic 避免由于HashFunction的不合理。过多的循环尝试。和Resize
            {
                Entry temp = entries[pos];
                if (temp == null)
                {
                    entries[pos] = current;
                    return true;
                }

                entries[pos] = current;
                current = temp;

                if (pos == Hash(hash1, current.key))
                {
                    pos = Hash(hash2, current.key);
                }
                else
                {
                    pos = Hash(hash1, current.key);
                }

                ++loop;
            }
            return false;
        }

        public bool ContainsKey(TKey key)
        {
            VerifyKey(key);
            int h1 = Hash(hash1, key);
            if (entries[h1] != null && comparer.Equals(entries[h1].key, key))
            {
                return true;
            }
            int h2 = Hash(hash2, key);
            if (entries[h2] != null && comparer.Equals(entries[h2].key, key))
            {
                return true;
            }

            if (conflictDic.ContainsKey(key))
                return true;

            return false;
            //throw new NotImplementedException();
        }

        public ICollection<TKey> Keys
        {
            get { throw new NotImplementedException(); }
        }

        public bool Remove(TKey key)
        {
            throw new NotImplementedException();
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            throw new NotImplementedException();
        }

        public ICollection<TValue> Values
        {
            get { throw new NotImplementedException(); }
        }

        public TValue this[TKey key]
        {
            get
            {
                throw new NotImplementedException();
            }
            set
            {
                throw new NotImplementedException();
            }
        }

        #endregion

        #region ICollection<KeyValuePair<TKey,TValue>> 成员

        public void Add(KeyValuePair<TKey, TValue> item)
        {
            throw new NotImplementedException();
        }

        public void Clear()
        {
            Entry[] newEntries = new Entry[entries.Length];
            entries = newEntries;
            conflictDic = new System.Collections.Generic.Dictionary<TKey, TValue>();
            size = 0;
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            throw new NotImplementedException();
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }

        public int Count
        {
            get { throw new NotImplementedException(); }
        }

        public bool IsReadOnly
        {
            get { throw new NotImplementedException(); }
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            throw new NotImplementedException();
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey,TValue>> 成员

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        #endregion

        #region IEnumerable 成员

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }

        #endregion
    }
}
